#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>
using namespace std;

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        unordered_map<long long, vector<int>> hash;
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; ++i) {
            hash[nums[i]].push_back(i);
        }
        int ret = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                long long a = (long long)2 * nums[i] - nums[j];
                if (hash.count(a)) {
                    for (auto k : hash[a]) {
                        if (k < i) {
                            dp[i][j] += dp[k][i] + 1;
                        }
                    }
                }
                ret += dp[i][j];
            }
        }
        return ret;
    }
    int lenLongestFibSubseq(vector<int>& arr) {
        int n = arr.size();
        unordered_map<int, int> hash;
        vector<vector<int>> dp(n, vector<int>(n, 2));
        for (int i = 0; i < n; ++i)
            hash[arr[i]] = i;
        int ret = 0;
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int a = arr[j] - arr[i];
                if (hash.count(a) && a < arr[i]) dp[i][j] = dp[hash[a]][i] + 1;
                ret = max(ret, dp[i][j]);
            }
        }
        return ret >= 3 ? ret : 0;
    }

    int longestSubsequence(vector<int>& arr, int difference) {
        int n = arr.size();
        unordered_map<int, int> hash;
        hash[arr[0]] = 1;
        int ret = 0;
        for (int i = 1; i < n; ++i) {
            hash[arr[i]] = hash[arr[i] - difference] + 1;
            ret = max(ret, hash[arr[i]]);
        }
        return ret;
    }

    bool checkPartitioning(string s) {
        int n = s.size();
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i; j < n; ++j) {
                if (s[i] == s[j]) {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
            }
        }
        for (int i = 1; i < n - 1; ++i) {
            for (int j = i; j < n - 1; ++j) {
                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][n - 1]) return true;
            }
        }
        return false;
    }

    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end(), [](vector<int> v1, vector<int> v2) {
            return v1[0] < v2[0];
            });

        vector<int> dp(n, 1);
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (pairs[j][1] < pairs[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp[n - 1];
    }

    struct TreeNode {
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode() : val(0), left(nullptr), right(nullptr) {}
        TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
        TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
        
    };

    int ret = INT_MIN;
    int maxgain(TreeNode* root) {
        if (!root) return 0;

        int leftgain = max(maxgain(root->left), 0);
        int rightgain = max(maxgain(root->right), 0);

        int p = root->val + leftgain + rightgain;
        ret = max(ret, p);

        return root->val + max(leftgain, rightgain);
    }

    int maxPathSum(TreeNode* root) {
        maxgain(root);
        return ret;
    }

    int ret = 0;
    int dfs(TreeNode* root, long long path, long long targetSum)
    {
        if (root == nullptr) return 0;
        int ret = 0;
        if (path == targetSum) ++ret;

        if (root->left)ret += dfs(root->left, path + root->left->val, targetSum);
        if (root->right)ret += dfs(root->right, path + root->right->val, targetSum);
        return ret;
    }

    int pathSum(TreeNode* root, int targetSum) {
        if (root == nullptr) return 0;
        int ret = 0;
        return dfs(root, root->val, targetSum) + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
    }

    void flatten(TreeNode* root) {
        while (root != nullptr)
        {
            if (root->left == nullptr) root = root->right;
            else
            {
                TreeNode* pre = root->left;
                while (pre->right)
                {
                    pre = pre->right;
                }
                pre->right = root->right;
                root->right = root->left;
                root->left = nullptr;
                root = root->right;
            }
        }
    }
};
